package com.leetcode;

import java.util.ArrayList;
import java.util.List;

/*数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：
输入：n = 1
输出：["()"]
 */
public class Leetcode022 {
//solutio 1 : 暴力解法，生成所有 2^{2n}个序列，再判断哪些是合法的序列
    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList<String>();
        generateAll(new char[2*n],0,combinations);
        return combinations;
    }

    private void generateAll(char[] current, int pos, List<String> combinations) {
        if(pos == current.length){
            if(isValid(current)){
                combinations.add(new String(current));
            }
        }else{
//            System.out.println(current.hashCode());
            //左括号递归
            current[pos]='(';
            generateAll(current,pos+1,combinations);
            //右括号递归
            current[pos]=')';
            generateAll(current,pos+1,combinations);
        }
    }
    //1）在结束时判断左右括号数量是否相等，如果不相等则返回false
    //2）在循环体内判断右括号比左括号的数量多，则非法，也就没必要再统计了。这是因为必须要先有左括号，然后才有右括号
    private boolean isValid(char[] current) {
        int balance = 0;
        for(int i=0; i<current.length; i++){
            if(current[i] == '('){
                balance ++;
            }else{
                balance --;
            }

            if(balance < 0){
                return false;
            }
        }

        return balance==0;
    }

/*
    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList<String>();
        generateAll("", combinations, n, n);
        return combinations;
    }

    //这里有个地方需要注意：subList只是临时变量，每次进行字符操作都会创建一个新的subList,因此当次循环的结果并不会影响后续的操作。
    private void generateAll(String subList, List<String> combinations, int left, int right) {
        if (left == 0 && right == 0){
//            System.out.println(subList.hashCode());
            combinations.add(subList);
            return;
        }

        //左括号优先，如果左括号大于0，则可以继续
        if(left > 0){
            generateAll(subList+"(",combinations,left -1 ,right);
        }

        //只有在左括号出现的情况下，右括号才能出现
        if(right > left){
            generateAll(subList+")",combinations,left ,right-1);
        }
    }
*/

    public static void main(String[] args) {
        Leetcode022 leetcode022 = new Leetcode022();
        System.out.println(leetcode022.generateParenthesis(3));
    }
}
